#include <vector>

using namespace std;


/**
 * @brief 713. 乘积小于 K 的子数组
 * https://leetcode.cn/problems/subarray-product-less-than-k/
 * [滑动窗口]
 * opt[i] = 距离 ith element 最远的 product < k 的位置
 */
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        size_t n = nums.size();

        vector<int> opt(n, 0);
        for (int i = 0; i < opt.size(); i++) opt[i] = i+1;

        int l = 0, r = 0;
        int product = 1;
        while (r < n && product < k) {
            product *= nums[r++];
        }
        r -= 1;  // nums[r] 需要在乘积里面

        for (int i = 0; i < r; i++) {
            opt[i] = 0;
        }

        while (r < n) {
            while (product >= k) {
                product /= nums[l++];
            }
            opt[r++] = l;
            if (r >= n) break;
            product *= nums[r];
        }

        // sum up
        int res = 0;
        for (int j = 0; j < opt.size(); j++) {
            res += (j - opt[j] + 1);
        }
        return res;
    }
};
